/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2024 —05 —05
 * Time: 11:50
 */
public class SolutionBinaryTree_preorder_inorder {
 /*   *//**//**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
    class Solution {

        public int preindex; // 默认值为0 //这里也有一个点注意，不要写成静态成员变量，在多个案例跑代码时，后台可能不会通过
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return  buildTreeChilde(preorder , inorder , 0 , preorder.length-1);

        }

        public TreeNode buildTreeChilde(int[] preorder , int[] inorder , int inbegin, int inend ){
            if(inend < inbegin){
                return null;
            }//这一步很关键，什么时候结束递归， 当inend的下标小于（可以等于）inbegin的时候就不在创建节点了
            TreeNode root = new TreeNode(preorder[preindex]);


            int rootindex = findIndexRoot(inorder , inbegin , inend , preorder[preindex] );//先找到下标，在加加
            if(rootindex == -1){
                return null;
            }
            preindex++;  //还有一个问题，这个preindex是一个局部变量，左树递的时候在++ 归回来之后就慢慢恢复初始值了，到右树的创立时，preindex应该是继续之前增长的值 增长，所以把preindex定义为全局变量更为妥当，这样它的值就不会还原了
            root.left = buildTreeChilde(preorder ,  inorder , inbegin, rootindex-1);
            root.right = buildTreeChilde(preorder ,  inorder , rootindex+1 , inend);
            return root;


        }
        public int findIndexRoot(int[] inorder , int inbegin , int inend , int key){//参数：前序遍历数组 ， 开始下标，结束下标，要找的元素（关键字），返回值为该元素的下标
            for( int i = inbegin ; i <= inend ; i++){
                if(inorder[i] == key){
                    return i;
                }

            }
            return -1;
        }
    }
}
